package ods;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Random;
import java.util.Set;

/**
 * An implementation of linear probing.  The hash method used is tabulation hashing.
 * @author morin
 *
 * @param <T>
 */
public class LinearHashTable<T> implements USet<T> {

	protected static final int w = 32;
	protected static final int r = 8;
	Factory<T> f;
	
	/**
	 * The table
	 */
	T[] t;   // the table
	
	/**
	 * Special marker - used to show deleted nodes
	 */
	T del;
	
	int n;   // the size
	int d;   // t.length = 2^d
	int q;   // number of non-null entries in t
	
	/**
	 * 
	 * @param nil an object of class T that will never be 
	 * stored in the table
	 */
	@SuppressWarnings("unchecked")
	public LinearHashTable(T nil) {
		this.del = nil;
		f = new Factory<T>((Class<T>)nil.getClass());
		d = 1;
		t = f.newArray(1<<d);
	}
	
	/**
	 * Resize the backing array to have size 2^d
	 * Warning: 2^d should be much bigger than n
	 * @param d
	 */
	protected void resize() {
		d = 1;
		while ((1<<d) < 3*n) d++;
		T[] told = t;
		t = f.newArray(1<<d);
		q = n;
		// insert everything in told
		for (int k = 0; k < told.length; k++) {
			if (told[k] != null && told[k] != del) {
				int i = hash(told[k]);
				while (t[i] != null) 
					i = (i == t.length-1) ? 0 : i + 1;
				t[i] = told[k];
			}
		}
	}

	protected int hash(T x) {
		int h = x.hashCode();
		return (tab[0][h&0xff] 
		         ^ tab[1][(h>>>8)&0xff]
		         ^ tab[2][(h>>>16)&0xff] 
		         ^ tab[3][(h>>>24)&0xff])
		  	    >>> (w-d);
	}

	/* sample code
	protected int idealHash(T x) {
		return tab[x.hashCode() >>> w-d];
	}
	*/

/*  this code is broken - repeatedly adding and removing the same element gives a big chain
	public boolean addSlow(T x) {
		if (2*(q+1) > t.length) resize();   // max 50% occupancy
		int i = hash(x);
		while (t[i] != null) {
			if (t[i] != del && x.equals(t[i])) return false;
			i = (i == t.length-1) ? 0 : i + 1; // increment i (mod t.length)
		}
		t[i] = x;
		n++; q++;
		return true;
	}
	*/
	
	public boolean add(T x) {
		if (find(x) != null) return false;
		if (2*(q+1) > t.length) resize();   // max 50% occupancy
		int i = hash(x);
		while (t[i] != null && t[i] != del)
			i = (i == t.length-1) ? 0 : i + 1; // increment i (mod t.length)
		if (t[i] == null) q++;
		n++;
		t[i] = x;
		return true;
	}

	/**
	 * A faster version of add(x)
	 * @param x
	 * @return
	 */
	public boolean add2(T x) {
		if (2*(q+1) > t.length) resize();   // max 50% occupancy
		int i = hash(x), j = -1;
		while (t[i] != null) {
			if (t[i] == del && j == -1) j = i;
			if (t[i] != del && t[i].equals(x)) return false;
			i = (i == t.length-1) ? 0 : i + 1; // increment i (mod t.length)
		}
		t[j == -1 ? i : j] = x;
		n++; q++;
		return true;
	}

	

	public T find(T x) {
		int i = hash(x);
		while (t[i] != null) {
			if (t[i] != del && x.equals(t[i])) return t[i];
			i = (i == t.length-1) ? 0 : i + 1; // increment i (mod t.length)
		}
		return null;
	}

	public T remove(T x) {
		int i = hash(x);
		while (t[i] != null) {
			T y = t[i];
			if (y != del && x.equals(y)) { 
				t[i] = del;
				n--;
				if (8*n < t.length) resize(); // min 12.5% occupancy
				return y;
			}
			i = (i == t.length-1) ? 0 : i + 1;  // increment i (mod t.length)
		}
		return null;
	}

	public int size() {
		return n;
	}
	
	public void clear() {
		n = 0;
		q = 0;
		d = 1;
		t = f.newArray(1<<d);
	}
	
	public Iterator<T> iterator() {
		class IT implements Iterator<T> {
			int i, iprev;
			public IT() {
				iprev = -1;
				i = 0;
				while (i < t.length && (t[i] == null || t[i] == del)) i++;
			}
			public boolean hasNext() {
				return i < t.length;
			}
			public T next() {
				T x = t[i];
				iprev = i;
				while (i < t.length && (t[i] == null || t[i] == del)) i++;		
				return x;
			}
			public void remove() {
				t[iprev] = del;
				n--;
			}
		};
		return new IT();
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Random rand = new Random(1);
		USet<Integer> lht = new LinearHashTable<Integer>(-1);
		Set<Integer> s = new HashSet<Integer>();
		int n = 1000000;
		System.out.println("Adding");
		for (int i = 0; i < n; i++) {
			Integer x = rand.nextInt(n);
			boolean rs = s.add(x);
			boolean rlht = lht.add(x);
			if (rs != rlht) 
				throw new RuntimeException("Aaaaaaaaaaaaaaaah!");
			if (s.size() != lht.size()) {
				System.out.println(s.size());
				System.out.println(lht.size());
				throw new RuntimeException("Bwaaaaaaaaaaaaaaah!");
			}
		}
		System.out.println("Searching");
		for (int i = 0; i < n; i++) {
			Integer x = rand.nextInt(n);
			boolean rs = s.contains(x);
			boolean rlht = lht.find(x) != null;
			if (rs != rlht) 
				throw new RuntimeException("Aaaaaaaaaaaaaaaah!");
			if (s.size() != lht.size()) 
				throw new RuntimeException("Bwaaaaaaaaaaaaaaah!");
		}

		System.out.println("Removing");
		for (int i = 0; i < n; i++) {
			Integer x = rand.nextInt(n);
			boolean rs = s.remove(x);
			boolean rlht = lht.remove(x) != null;
			if (rs != rlht) 
				throw new RuntimeException("Aaaaaaaaaaaaaaaah!");
			if (s.size() != lht.size()) 
				throw new RuntimeException("Bwaaaaaaaaaaaaaaah!");
		}
		s.clear();
		lht.clear();
	}
	
	/**
	 * Table used by tabular hashing
	 */
	protected static int[][] tab =
	{{0x0069aeff,
		0x6ac0719e,
		0x384cd7ee,
		0xcba78313,
		0x133ef89a,
		0xb37979e6,
		0xa4c4e09c,
		0x911c738b,
		0xc7fe9194,
		0xba8e5dc7,
		0xe610718c,
		0x48460ac5,
		0x6b4d9d43,
		0x73afeeab,
		0x051264cb,
		0x4b3dba93,
		0x28837665,
		0xfb80a52b,
		0xad1c14af,
		0xb2baf17f,
		0x35e311a5,
		0xf7fa2905,
		0xa973c315,
		0x00885f47,
		0x8842622b,
		0x0445a92c,
		0x701ba3a0,
		0xef608902,
		0x176099ad,
		0xd240f938,
		0xb32d83c6,
		0xb341afb8,
		0xc3a978fb,
		0x55ed1f0c,
		0xb581286e,
		0x8ff6938e,
		0x9f11c1c5,
		0x4d083bd6,
		0x1aacc2a4,
		0xdf13f00a,
		0x1e282712,
		0x772d354b,
		0x21e3a7fd,
		0x4bc932dc,
		0xe1deb7ba,
		0x5e868b8a,
		0xc9331cc6,
		0xaa931bbf,
		0xff92aba6,
		0xe3efc69f,
		0xda3b8e2a,
		0xf9b21ec1,
		0x2fb89674,
		0x61c87462,
		0xa553c2f9,
		0xca01e279,
		0x35999337,
		0xf44c4fd3,
		0x136a2773,
		0x812607a8,
		0xbfcd9bbf,
		0x0b1d15cd,
		0xc2a0038b,
		0x029ab4f7,
		0xcd7c58f9,
		0xed3821c4,
		0x325457c6,
		0x1dc6b295,
		0x876dcb83,
		0x52df45fc,
		0xa01c9fba,
		0xc938ff66,
		0x19e52c87,
		0x03ae67f9,
		0x7db39e51,
		0x74f31686,
		0x5f10e5a3,
		0x74108d8a,
		0x64e63104,
		0xd86a38d6,
		0x65be2fbb,
		0xef06049e,
		0x9bca1dbd,
		0x06c63e73,
		0xe97bd103,
		0xfed3c22c,
		0x09d10fc6,
		0xb92633a3,
		0x21378ebf,
		0xe37fa54e,
		0x893c7910,
		0xc1c74a5a,
		0x6c23c029,
		0x4d4b6187,
		0xd72bb8fb,
		0x0dbe1118,
		0x5e0f4188,
		0xce0d2dc8,
		0x8dd83231,
		0x0466ab90,
		0x814bc11a,
		0xef688b9b,
		0x0a03c851,
		0xca3c984f,
		0x6df87ca4,
		0x6b34d1b2,
		0x2bad5c75,
		0xaed1b6d8,
		0x8c73f8b4,
		0x4577d798,
		0x5c953767,
		0xe7da2d51,
		0x2b9279a0,
		0x418d9b51,
		0x8c47ec3d,
		0x894e6119,
		0xa0ca769d,
		0x1c3b16a4,
		0xa1621b5b,
		0xa695da53,
		0x22462819,
		0xf4b878cf,
		0x72b4d648,
		0x1faf4267,
		0x4ba16750,
		0x08a9d645,
		0x6bfb829c,
		0xe051295f,
		0x6dd5cd97,
		0x2e9d1baf,
		0x6ed6231d,
		0x6f84cb25,
		0x9ae60c95,
		0xbcee55ca,
		0x6831cd97,
		0x2ccdbc99,
		0x9f8a0a81,
		0xa0b2c08f,
		0xe957c36b,
		0x9cb797b5,
		0x107c6362,
		0x48dacf5d,
		0x6e16f569,
		0x39be78c3,
		0x6445637f,
		0xed445ee5,
		0x8ec45004,
		0x9ef8a405,
		0xb5796a45,
		0x049d5143,
		0xb3c1d852,
		0xc36d9b44,
		0xab0da981,
		0xff5226b3,
		0x19169b4c,
		0x9a49194d,
		0xba218b42,
		0xab98c8ee,
		0x4db02645,
		0x6faca3c8,
		0x12c60d2d,
		0xaf67b750,
		0xf0f6a855,
		0xead566d9,
		0x42d0cccd,
		0x76a532bb,
		0x82a6dc35,
		0xc1c23d0e,
		0x83d45bd2,
		0xd7024912,
		0x97888901,
		0x2b7cdd2c,
		0x523742a5,
		0xecb96b3b,
		0xd800d833,
		0x7b4d0c91,
		0x95c7dd86,
		0x88880aad,
		0xf0ce0990,
		0x7e292a90,
		0x79ac4437,
		0x8a9f59cc,
		0x818444d1,
		0xae4e735d,
		0xa529db95,
		0x58b35661,
		0xa909a7de,
		0x9273beaa,
		0xfe94332c,
		0x259b88e4,
		0xc88f4f6a,
		0x2a9d33ef,
		0x4b5d106d,
		0xdc3a9fca,
		0xa8061cad,
		0x7679422c,
		0xaf72ad02,
		0xc5799ea5,
		0x306d694d,
		0x620aad10,
		0xd188b9dd,
		0xeff6ad87,
		0x6b890354,
		0xb5907cd3,
		0x733290fc,
		0x4b6c0733,
		0x0bad0ebd,
		0xa049d3ad,
		0xc9d0cdae,
		0x9c144d6f,
		0x5990b63b,
		0xfa33d8e2,
		0x9ebeb5a0,
		0xbc7c5c92,
		0xd3edd2e6,
		0x54ae1af6,
		0xd6ada4bd,
		0x14094c5a,
		0x0e3c5adf,
		0xf1ab60f1,
		0x74456a66,
		0x0f3a675a,
		0x87445d0d,
		0xa81adc2e,
		0x0f47a1a5,
		0x4eedb844,
		0x9c9cb0ce,
		0x8bb3d330,
		0x02df93e6,
		0x86e3ad51,
		0x1c1072b9,
		0xacf3001b,
		0xbd08c487,
		0xc2667a11,
		0xdd5ef664,
		0xd47b67fb,
		0x959cca45,
		0xa7da8e68,
		0xb75b1e18,
		0x75201924,
		0xe689ab8b,
		0x0f5e6b0a,
		0x75205923,
		0xbba35593,
		0xd24dab24,
		0x0288caeb,
		0xcbf022a9,
		0x392d7ee5,
		0x16fe493a,
		0xb6bcadfd,
		0x9813ec72,
		0x9aa3d37c,
		0xee88a59e,
		0x6cdbad4e,
		0x6b96aabf,
		0xcb54d5e5},
		{0x116fc403,
		0x260d7e7b,
		0xdef689e7,
		0xa5b3d49a,
		0x921f3594,
		0xb24c8cba,
		0x1bdefb3f,
		0x6519e846,
		0x24b37253,
		0x1cc6b12b,
		0x6f48f06e,
		0xca90b0db,
		0x8e20570b,
		0xda75ed0f,
		0x1b515143,
		0x0990a659,
		0xdcedb6b3,
		0xec22de79,
		0xdd56f7a9,
		0x901194a6,
		0x4bf3db02,
		0x5d31787d,
		0xd24da2ca,
		0x9fc9bc14,
		0x9aa38ac9,
		0xe95972ba,
		0x8233a732,
		0xb9d4317e,
		0x51f9b329,
		0x94f12c56,
		0x1ace26e4,
		0xecda5183,
		0x1353e547,
		0x39b99ab3,
		0x6413ac97,
		0xeb6b5334,
		0xdd94ed2b,
		0x298e9d2c,
		0xd38abc91,
		0x3f17ee4e,
		0x99f8931d,
		0x88bae7da,
		0xb5506a36,
		0x2d7baf6d,
		0x42a98d2b,
		0xbb9b94b9,
		0x58820083,
		0x521bba4c,
		0x76699597,
		0x137b86be,
		0x8533888e,
		0xb37316dd,
		0x284c3de4,
		0xfe60e3e6,
		0x94edaa40,
		0x919c85cd,
		0x24cb6f23,
		0x6b446fbd,
		0xbe933c15,
		0x2a43951a,
		0x791a9f90,
		0x47977c04,
		0xa6350eec,
		0x95e817a5,
		0xffc82e8c,
		0xad379229,
		0x6ec9531a,
		0x8cab29f9,
		0xb2f18402,
		0xd0ebdac1,
		0xd7b559b4,
		0x7ad30e7c,
		0xe1d1adb7,
		0x58a66f9c,
		0x7a26636a,
		0x8c865f92,
		0x65363517,
		0x732b87db,
		0x64a1ad52,
		0x72e87c39,
		0x0b943e4d,
		0x532d3593,
		0xedcf9975,
		0x44b5bec1,
		0x13ac91f8,
		0x6e6f3a76,
		0x36ac3c6d,
		0x528a3ecf,
		0xf3d8cd75,
		0x8facd64c,
		0xdb4d13d5,
		0x80d49a67,
		0xaa7061d3,
		0x9486ba8d,
		0x7454a65b,
		0x18e7b707,
		0xd9cc05b9,
		0x44eb014d,
		0x28ba26d8,
		0xa8852791,
		0xf8dc3053,
		0xabe46b52,
		0x9e261d1f,
		0x768f83dd,
		0x1c888838,
		0x6d9b9ce6,
		0x69e82575,
		0x2959538f,
		0xd0ff9685,
		0x92b4540c,
		0x7c93035b,
		0x7cad90ad,
		0x49aaa908,
		0x3981f4b8,
		0x191f4339,
		0xd0971bfc,
		0xa7209692,
		0x0e253cad,
		0x40e2ee61,
		0xc5c63486,
		0xdf4f238b,
		0x2d3cb89a,
		0x3b5704b2,
		0xcc14c2cb,
		0xb1698d38,
		0x079c3b9b,
		0xbb3867e4,
		0x9f01e223,
		0x35e69012,
		0x5c87d888,
		0x2cea4193,
		0xee088da5,
		0x0ea4d5ab,
		0x8a4906e8,
		0xf6e5e283,
		0xee87fa18,
		0x9f96c751,
		0x947252c0,
		0x9b50b97e,
		0x05952521,
		0x9440f5ae,
		0xa0642786,
		0xebcc62be,
		0xadccf011,
		0x00b863e6,
		0x1c3ab5b3,
		0x7c701e4b,
		0xa9565792,
		0xb1ad459c,
		0x833ba164,
		0x89544ae3,
		0x35540c75,
		0x198d0fec,
		0xbe93bf33,
		0xc28444b3,
		0xbc3add48,
		0xb4300c14,
		0xee0ed408,
		0xca08ada3,
		0x0be06480,
		0xc4dd8ce2,
		0x61195564,
		0x5b10a111,
		0x65cd2b3b,
		0xcbeb06ae,
		0xfce70080,
		0xef40b102,
		0xfc0bfe6f,
		0x8111bf20,
		0xfb166db1,
		0x3598b2ef,
		0x1e0e04de,
		0x1bf7cf2d,
		0x0de7eaf1,
		0x829457e0,
		0xe8865341,
		0x826272ad,
		0xb57db2a4,
		0x7413e6e7,
		0x416323ff,
		0x8e08d503,
		0x1da4dfac,
		0x983b9a78,
		0x0fab5fe0,
		0x585e7a90,
		0x038cf73c,
		0xecf90d31,
		0x046055c8,
		0x59926d71,
		0x06959f1f,
		0x3b8290b7,
		0x0bb834d9,
		0xa0dc5bec,
		0xec9ae604,
		0x6ebfd59d,
		0xfeccbab5,
		0x240bd4ba,
		0x2df2b232,
		0xe14e0383,
		0xd86526ec,
		0xe3d974fc,
		0x940662b5,
		0x81abf5d4,
		0x8010e6eb,
		0x700d9849,
		0x040d0c42,
		0xc980417b,
		0x95fa374a,
		0x724b1448,
		0x217205ec,
		0x0153b4bb,
		0xea55ea92,
		0x2049d5a1,
		0x82576f06,
		0x586fcfeb,
		0xa975e489,
		0x14c862e9,
		0xacb8b52c,
		0x2f3fb91e,
		0xce273650,
		0x66608f4a,
		0x24f81bb7,
		0x0382dc34,
		0x07bdc163,
		0xc42ad034,
		0xe63cf998,
		0x1a61f233,
		0xd5754ebe,
		0x37275214,
		0x2322de2a,
		0x3a53b9b4,
		0xab9c6963,
		0x2f3a51be,
		0x5066e7c7,
		0x941bda97,
		0x75fadceb,
		0xd05ad081,
		0xf77d5daf,
		0xd9879250,
		0xebf8bf97,
		0x65be4a70,
		0x388eda48,
		0x728173fb,
		0x05975bfa,
		0x314dad8a,
		0x2cb4909f,
		0xc736b716,
		0x9007296d,
		0x4fd61551,
		0xd4378ccf,
		0x649aac3e,
		0xd9ca1a9d,
		0x16ff16ae,
		0x8090f1c5,
		0xfe0c4703,
		0xc4152307},
		{0xf07e5e34,
		0x62114ba6,
		0xf45ffe22,
		0xbaa48702,
		0xe27e48a4,
		0xc43b4779,
		0x549a4566,
		0x93bc4836,
		0x3b2e8d46,
		0x3f8a77ae,
		0x71e2d944,
		0xc09c5dce,
		0xebfbfd4f,
		0x7f8e1c40,
		0x3c310a69,
		0x52f62f09,
		0xb7fd11bb,
		0xa9d055a7,
		0xe3bd4654,
		0x9696ae10,
		0xdf953225,
		0x42fd2380,
		0x69756e5c,
		0x9d950bc4,
		0xe2beea59,
		0xd33daa07,
		0xe97d31ce,
		0xd9fb0a49,
		0x553a27f2,
		0x7166586f,
		0xeb04d48c,
		0x72adb63a,
		0x340ab99e,
		0x459b4609,
		0x481421b7,
		0x7db83c71,
		0x192f6c22,
		0x711852a8,
		0xc6bd6562,
		0xb91be2c8,
		0xefe89dbf,
		0xc404eb9b,
		0x9ebc1bc7,
		0x8dc7eed2,
		0x4d84efd7,
		0x0783d7e5,
		0x3b5ca2f2,
		0x9997e51c,
		0x89b432c9,
		0x72ae9672,
		0x61d522d9,
		0xa639fd45,
		0xa7da3b46,
		0x696e73ec,
		0x89581a95,
		0x4aa25f94,
		0xd0eb2a48,
		0x04865f68,
		0x1cbd651a,
		0xd6b2afd9,
		0xd401b965,
		0xd20aa5a7,
		0xc0aa1b15,
		0xfb4ce7af,
		0x159974c5,
		0x15d0841d,
		0x6b2836b4,
		0xef3b3edf,
		0xaf2db0b3,
		0x13106fb6,
		0xff41d7f9,
		0xab2a698d,
		0x68e04dc9,
		0xe5ee0099,
		0xe50d4017,
		0x5ea78d6d,
		0x2e18fb07,
		0xfe22b9ff,
		0x544c05f1,
		0xc2e10853,
		0x8d151bd6,
		0x17ee763a,
		0xa663ce31,
		0x4a4b5e33,
		0x298b13c1,
		0xd3b40c89,
		0x121b6b4e,
		0x59cf0429,
		0x3d0bab9d,
		0xd24c5dfe,
		0x5bb7349f,
		0xac5dbfe9,
		0x7eca5ebb,
		0xadb8b3e3,
		0x71ab540b,
		0xc8e3dc0d,
		0x12e6cd3f,
		0x8197f22c,
		0x5ff77265,
		0xe5641dbc,
		0x818ab24c,
		0x627b98f7,
		0xdd84e1d6,
		0x531c2346,
		0xec2f4e3c,
		0x4a3cb318,
		0x70cb24fe,
		0x35c17bfe,
		0xec91fd18,
		0x6efb3c18,
		0x16908369,
		0x41732188,
		0x449e658b,
		0x2e9931cb,
		0x67cd066e,
		0x883ca306,
		0xf66aecac,
		0x979bf015,
		0x8e85e27d,
		0x0560372b,
		0x987995d6,
		0xaff98ed7,
		0x552ee87b,
		0x21a53787,
		0x3d3cfd45,
		0xa084dae0,
		0x8c91be2f,
		0xac4c3550,
		0xa7db63ff,
		0x124b2f23,
		0x95d05d4e,
		0xb983db13,
		0xa929a3c1,
		0x111cd0a0,
		0xf59ded9a,
		0xce677ae3,
		0xfa949e59,
		0xd673e658,
		0xf8c8e27b,
		0x3c60fc3d,
		0x59a4f230,
		0xf54a5e87,
		0x08cff440,
		0xd4bbb1ee,
		0x6a0c7db0,
		0xecbaa99d,
		0xec61dcaf,
		0xf1056e2b,
		0x54236899,
		0xadad347c,
		0xc9885bc9,
		0x2fe2a4ec,
		0x01ba2b86,
		0x6b23f604,
		0xb354ef08,
		0x6a3dc5e2,
		0xab61da36,
		0x7543925a,
		0x0a558940,
		0x48d4d8f3,
		0xd84f2f6f,
		0x6ac5311c,
		0xcd1b660e,
		0x51293d3d,
		0xa0f15790,
		0xd629cd78,
		0x89201fa5,
		0x46005119,
		0x9617fa14,
		0xc375a68b,
		0x7ccb519b,
		0x6420a714,
		0xb736d2ce,
		0x154fcf4a,
		0x71cad2f5,
		0xacb150d7,
		0x97bc8e36,
		0xc5506d0a,
		0xa9facc35,
		0x1a9630db,
		0xbd3d72ee,
		0x58cdf27c,
		0x17f3e1f9,
		0x41598836,
		0xd6adac30,
		0x309a5b3f,
		0x3bd3aa32,
		0x40f08f50,
		0xf37cbd6c,
		0xcbdb8aef,
		0xe0819189,
		0x5a9b663b,
		0x6932a448,
		0xb1b3e866,
		0xc50ee24d,
		0xad999126,
		0xafb04056,
		0xc95974e5,
		0x636a64fa,
		0x0bb12dd9,
		0x78caa164,
		0xd26a7ec8,
		0x451a0b53,
		0x6d00aac6,
		0x484d1d9d,
		0x39728dd4,
		0xfbfec2ea,
		0xa6d5aaf9,
		0x91c4f6ea,
		0x31cab009,
		0x9b6ba4e8,
		0xe271ed67,
		0x4c87a84d,
		0x8a1a4567,
		0x93749497,
		0xc566edcc,
		0xc8229554,
		0x927925fd,
		0xad1caced,
		0xdc24f7ed,
		0xc92b9220,
		0x936cd037,
		0xbd2d0256,
		0x5c92409b,
		0xa3aa2682,
		0x4da97646,
		0xbcfdec81,
		0x25d5b61d,
		0x20e1660d,
		0x4b5214ed,
		0x91aa596a,
		0xb241415c,
		0x88ec91a1,
		0x2375e939,
		0x981ad627,
		0x4a54ee18,
		0x13d98660,
		0x9375c64d,
		0x538d3b28,
		0x4bf37ca7,
		0x192b351e,
		0x3cacf215,
		0x3ecf3565,
		0x50f5c0fc,
		0xaafe3d4e,
		0x6351b4f5,
		0x1b800d4f,
		0xfad73cdf,
		0xe300e1d8,
		0xb2cb5b04,
		0xfb019702,
		0xfb647f85,
		0x375a7b74,
		0xed6a6760,
		0x45c54e76,
		0x06524d79},
		{0x48722ec4,
		0x8a2694db,
		0x3cf80478,
		0xf9bc47ba,
		0x76b258fb,
		0xf71a1ec6,
		0x841189df,
		0x1a866461,
		0x72b5488c,
		0x71663983,
		0xbda59407,
		0xa2b68f85,
		0x62dbd0aa,
		0xe4966aa3,
		0x32e0efaa,
		0x71bb3699,
		0x2eda14a6,
		0x53f8917c,
		0x874974ce,
		0xe680bcca,
		0x96a9c462,
		0x399ca451,
		0xc46616f5,
		0xeee71114,
		0x5878e472,
		0x3a83c559,
		0x54862a18,
		0x82aea480,
		0x492d0019,
		0xd62a7027,
		0x36655f50,
		0xce412fdf,
		0xc8136871,
		0xd6cfe1d8,
		0x121c9c91,
		0x13abbf51,
		0x3aaa7037,
		0x9f6e7cb6,
		0xae82c4c4,
		0x55fdce32,
		0xd8dd6bda,
		0xd6ec4938,
		0x6a5aee52,
		0x52c8a764,
		0xa6a85297,
		0x5131de9e,
		0x396a6599,
		0xe27b1100,
		0xe68588d3,
		0x7b89a612,
		0xad48a7a4,
		0xfd205673,
		0x81807089,
		0x239d2d38,
		0x39518df3,
		0x256f3f14,
		0x5c65e7b8,
		0x64caebdc,
		0xd8d694b6,
		0xb4a87da3,
		0xa651881e,
		0xca1d252d,
		0x993a3ddc,
		0x14f9a54d,
		0x6b14d2ff,
		0xbbed03bb,
		0x8d12bc03,
		0x6cce455d,
		0x613d6487,
		0x6d04ce6a,
		0xc2f4c84c,
		0x306d8ff2,
		0x584a9847,
		0x68902fc5,
		0x70af1a4f,
		0x3ab4cb98,
		0xe8be4453,
		0x7e95d355,
		0x84b0f371,
		0x4c5ccb52,
		0xdd6d029c,
		0xafa47124,
		0x71aabf91,
		0xd3407f95,
		0xe7fa3a9c,
		0x4f634405,
		0x0cbf2cb7,
		0x0192ff17,
		0x296959dd,
		0x9e4d34d5,
		0xfd9a4286,
		0xac7b6933,
		0x4650f585,
		0x168af40d,
		0x73816119,
		0x5542d96d,
		0x99047276,
		0x1b5bbe67,
		0x01a8209e,
		0x6f9db32e,
		0xd762bbd1,
		0x299a3804,
		0x87abe66d,
		0xd479eeaa,
		0x79928f4e,
		0x3937ffbc,
		0x3c8e83ca,
		0x2a8f9347,
		0x4d2324d3,
		0xf0183dda,
		0x9fbedb15,
		0xac365889,
		0xf1be552c,
		0xa4b32d5a,
		0xdc77fff3,
		0x9d516da8,
		0x7f3c347c,
		0x39e8479f,
		0x9e869687,
		0x6a160347,
		0x49ab7403,
		0x830d31c7,
		0x11311354,
		0x79e6cc69,
		0x35b25caa,
		0x398af9aa,
		0x02ef4356,
		0xb5ecba53,
		0x666d6c8b,
		0x8836b3ae,
		0x23b9fc98,
		0x0cc8e3d0,
		0x3ad594e1,
		0xb124529d,
		0xe059c1de,
		0xfa88e0d9,
		0xba117846,
		0x1782a65a,
		0xee9f80f9,
		0xbc9aec55,
		0x88aec1d4,
		0x9c3907fa,
		0x92b7b5bf,
		0x464acbf4,
		0xbbbd04a8,
		0xf0e966bf,
		0x14c5f971,
		0x83018d49,
		0xfaf4fc0a,
		0x3b4639b2,
		0x6b7e297d,
		0xc0e9a807,
		0x418713d3,
		0x1a2b2361,
		0x80850d90,
		0xd515816e,
		0x3deb48ea,
		0x6bfe6aa1,
		0x3680036c,
		0x228e76ae,
		0x78f16c87,
		0xff4d85ea,
		0x7d831974,
		0xba962d6b,
		0x4bae0b1d,
		0xc0db431a,
		0x04b46400,
		0xcf427175,
		0x244e321d,
		0x1c8b1fc9,
		0x63a2b794,
		0x1939d9c6,
		0xc92a530e,
		0x21a8e5ad,
		0x28050194,
		0x3b106223,
		0xb21e2ce1,
		0x7ae71fe4,
		0x7f7759f0,
		0x0329c8f4,
		0xd09f6b37,
		0x897e12a5,
		0x4103c4b1,
		0x56520dae,
		0x5d7391aa,
		0x7ac9f12d,
		0xeac6b834,
		0x99f8f6a8,
		0x2867867a,
		0xff6f3343,
		0x3167097a,
		0x38432d1d,
		0x108377f8,
		0xfd8e0d5f,
		0x25e15692,
		0xf00d40f9,
		0x1f1276f3,
		0xb748c8cd,
		0x6dbb9d9c,
		0x99ab7ceb,
		0xa4a9784f,
		0xcb4b2535,
		0xb3eb5ca7,
		0xd3a09e75,
		0x90f3ee7e,
		0x28ef2a57,
		0xbdb643a2,
		0x1112ab10,
		0x546b1af2,
		0x8c41e90d,
		0x0f5fcd88,
		0x6f259f40,
		0x34b33966,
		0x5f3558d7,
		0xfff36f0b,
		0xa3459449,
		0xdcecbce1,
		0x69ff2bf7,
		0x7525e1da,
		0x24c9de72,
		0xea9626b1,
		0x87c7385d,
		0x15e4211e,
		0x9f7ef269,
		0xfed018d1,
		0x7632076c,
		0x8d4f0157,
		0x10c1205a,
		0x65db0e00,
		0x813f0e8b,
		0xbafea255,
		0xb47e6663,
		0x2a0eba78,
		0xf66b3783,
		0xfff1db48,
		0x47997f03,
		0x3a49e877,
		0x4536a0b5,
		0x89b0738f,
		0xf5758b5e,
		0x1d277388,
		0xf5db28e8,
		0xb4ef0add,
		0x776fed12,
		0x045b614a,
		0xc95f47ae,
		0x13a1d602,
		0x217d6338,
		0xc509d080,
		0x006789de,
		0xd891cccc,
		0xb02f9980,
		0x67f00301,
		0xafc87999,
		0x043d8fbd,
		0xb32d6061}};
}
